package DP.Lesson7;

/**
 * https://leetcode-cn.com/problems/maximal-square/
 * 求最大都是1 的正方形多大。 这个很巧妙
 * dp是到当前位置的，最大的边。因为这是 正方形，所以，要找更大的就是要往右下角找
 * 右下角的地方，就看 左边、上边、左上角 这三个点谁的边最长
 *
 * 在计算的时候，用到了 min，因为如果是正方形的话，他肯定是1的
 *
 * dp[i][j] = max{min([i-1][j],min[i][j-1], min[i-1][j-1]) + 1}
 */
public class MaximunSquare {

    public int maximalSquare(char[][] matrix) {
        int m = matrix.length;
        if(m==0) return 0;
        int n = matrix[0].length,i,j;

        //开+1 是为了方便后面代码判断
        int[][] dp = new int[m][n];
        int res = 0;
        for(i=0;i<m;i++){
            for(j=0;j<n;j++){
                //处理靠边是1的情况，记得括号，是有一个0，然后，等于1
                if( (i==0 || j == 0) && matrix[i][j] == '1'){
                    dp[i][j] = 1;
                    res = Math.max(res, dp[i][j]);//因为每行的第一个都是重新算的，这个要max下，看是不是右边的那个大
                    continue;
                }
                if(matrix[i][j] == '1'){
                    dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i-1][j-1], dp[i][j-1])) + 1;
                    res = Math.max(res, dp[i][j]);
                }
            }
        }

        //注意，我们记录的是边，这里还要 相乘
        return res * res;
    }



    public static void main(String[] args){
        char[][] m = new char[4][5];
        m[0] = new char[]{'1','0','1','0','0'};
        m[1] = new char[]{'1','0','1','1','1'};
        m[2] = new char[]{'1','1','1','1','1'};
        m[3] = new char[]{'1','0','0','1','0'};
//        char[][] m = new char[1][1];
//        m[0] = new char[]{'0'};
        MaximunSquare mm = new MaximunSquare();
        mm.maximalSquare(m);
    }


}
